package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.Arrays;
import java.util.Scanner;

/*
有n个人，第i个人重量为wi。每艘船的最大载重量均为C，且最多只能乘两个人。用最少的船装载所有人。
求需要船的数量

贪心策略：
考虑最轻的人i，如果每个人都无法和他一起坐船（重量和超过C），
则唯一的方案是每个人坐一艘
否则，他应该选择能和他一起坐船的人中最重的一个j

in
10
1 2 3 4 5 6 7 8 9 10
10

out
6
 */
public class f乘船问题by贪心 {
	public static void main(String[] args) {
		f乘船问题by贪心 test = new f乘船问题by贪心();
		test.useGreedyAlgorithmBoat();
	}
	
	/**
	 * 前置方法
	 */
	public void useGreedyAlgorithmBoat() {
		Scanner scanner = new Scanner(System.in);
		int N = scanner.nextInt();
		int[] weight = new int[N];
		for (int i = 0; i < N; i++) {
			weight[i] = scanner.nextInt();
		}
		int maxWeight = scanner.nextInt();
		Arrays.sort(weight);
		int res = GreedyAlgorithmBoat(weight, N, maxWeight);
		System.out.println(res);
	}
	
	/**
	 * 贪心
	 * 双指针
	 * @param weight
	 * @param N
	 * @param maxWeight
	 * @return
	 */
	public int GreedyAlgorithmBoat(int[] weight, int N, int maxWeight) {
		int res = 0;
		int left = 0;
		int right = N - 1;
		while (N > 0) {
			if (weight[left] + weight[right] <= maxWeight) {
				right--;
				left++;
				N -= 2;
				res++;
			} else {
				right--;
				N--;
				res++;
			}
		}
		return res;
	}
}
